A programmable logic device (PLD) is a digital circuit implementation platform that can be configured by the end user to implement a logic circuit of their choice. The two most common types of PLDs are field-programmable gate arrays (FPGAs) and complex programmable logic devices (CPLDs). Many PLD vendors provide computed-aided design tools to help their customers to implement logic designs in their PLDs. One type of PLD, the FPGA, is used as an example to illustrate the invention. It should be noted that, in addition to PLDS, the invention is applicable to other integrated circuit implementation technologies, for example, application specific integrated circuits (ASICs), mask-programmed gate arrays, and standard cell devices.
In a conventional architecture, an FPGA includes an array of configurable logic blocks (CLBs) surrounded by programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a hierarchy of programmable routing resources, which are comprised of metal wire segments and programmable routing switches, also referred to as programmable interconnection points (PIPs). These CLBs, IOBs, and programmable routing resources are customized by loading a configuration bitstream into the FPGA. State-of-the art FPGAs contain tens of thousands of CLBs. For such devices, the task of establishing the required interconnections between the primitive cells inside a CLB and between the CLBs themselves becomes so onerous that it can only be accomplished within a reasonable amount of time with the assistance of computed-aided design tools. Accordingly, the manufacturers of FPGAs have developed place and route software tools which may be used by end customers to implement their respective designs in their FPGAs.
Routing tools are very important in determining the performance of a circuit implemented within an FPGA. If signals are not routed properly, an excessive amount of resources are used to carry signals. This could lead to a design with poor timing and power performance. Furthermore, routing tools are very difficult to develop and very time consuming to execute. Consequently, it is important to improve routing tools.